package com.leetcode.array;

public class BestTimeToBuyAndSellStockIII {

	public static void main(String[] args) {
		int[] nums = { 7,1,2,1,3,2,3, 6, 4 };
		int result = maxProfit(nums);
		System.out.println(result);
	}

	public static int maxProfit(int[] prices) {
		int len = prices.length;
		int j = len - 1;
		int i = j - 1;
		int max = 0, sum = 0;
		int k = i - 1;
		int mini=0;
		for (j = len - 1, i = j - 1; j > i && i >= 0;) {
			if (prices[j] <= prices[i]) {
				j = i;
				i = j - 1;
			} else {
				for(k=i-1;k>=1&&max<prices[j]-prices[i];){
					while(max<prices[j]-prices[i]){
					max=prices[j]-prices[i];
					mini=i;
					i--;
					}
					while(prices[k]<prices[mini]){
						k--;
					}
					sum+=max; max=0;
					if(k<1){
						break;
					}else{
					j=k;
					i=j-1;
					}
					
				}
				
			}
		}
		return sum;
	}
}
